public class ConstructMaximumBinaryTree {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int n = nums.length;
        int max = max(nums, 0, n - 1);
        TreeNode root = new TreeNode(nums[max]);
        process(root, 0, max - 1, nums, true);
        process(root, max + 1, n - 1, nums, false);
        return root;
    }

    public void process(TreeNode node, int start, int end, int[] nums, boolean flag) {
        if (start > end) return;
        int max = max(nums, start, end);
        TreeNode treeNode = new TreeNode(nums[max]);
        if (flag) {
            node.left = treeNode;
        } else node.right = treeNode;
        if (start == end) return;
        process(treeNode, max + 1, end, nums, false);
        process(treeNode, start, max - 1, nums, true);
    }

    public int max(int[] nums, int l, int r) {
        int ans = l;
        for (int i = l; i <= r; i++) {
            if (nums[i] > nums[ans]) ans = i;
        }
        return ans;
    }
}
